//题目:
// 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
// 对于每个单元格，你可以往上，下，左，右四个方向移动。 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
#include<iostream>
#include<vector>

using namespace std;
//代码:
class Solution 
{
    int arr[201][201]={0};
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
public:
    int dfs(vector<vector<int>>& matrix,int row,int col)
    {
        if(arr[row][col]!=0)return arr[row][col];
        int ret=1;//本身长度
        for(int i=0;i<4;i++)
        {
            int x=row+dx[i],y=col+dy[i];
            if(x>=0 && x<matrix.size() && y>=0 && y<matrix[0].size() && matrix[x][y]>matrix[row][col])
            {
                ret=max(ret,1+dfs(matrix,x,y));
            }
        }
        arr[row][col]=ret;
        return ret;
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) 
    {
        int ret=0;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                ret=max(ret,dfs(matrix,i,j));
            }
        }
        return ret;
    }
};